package com.swjd.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 插入排序
 *
 * @author 刘涛
 * @create 2021/9/27 22:17
 */
public class InsertSort {
    public static void main(String[] args) {
//        int arr[] = {101, 34, 119, 1};
//        insertSort(arr);

        //测试插入排序速度 O(n^2) 8万个数据测试
        Date date2 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date2);
        System.out.println("排序前的时间" + format);
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000);//生成[0,8000000)
        }
        insertSort(arr);
        Date date = new Date();
        String format2 = simpleDateFormat.format(date);
        System.out.println("排序前的时间" + format2);

    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //第一个数(即下标为0)直接放有序队列，然后其他数（即下标从1开始）依次插入有序队列
            //定义待插入的数
            int insertVal = arr[i];
            //插入数的前一个下标
            int insertIndex = i - 1;
            //给insertVal找到插入位置  （防止下标越界并且插入数小于前一个数）
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                //将要插入的数和前一个数交换位置
//                arr[i] = arr[insertIndex];//插入的数=前一个数
                arr[insertIndex + 1] = arr[insertIndex];//插入的数=前一个数 代码优化
                arr[insertIndex] = insertVal;//前一个数=插入数的值
                //将坐标往前移，以比较下一个值
                insertIndex--;
//                i--; 代码优化
            }
//            System.out.println(Arrays.toString(arr));
        }
    }
}
